Exclusive time of function

Time: O(N); Space: O(N); medium

On a single threaded CPU, we execute some functions. Each function has a unique id between 0 and N-1.

We store logs in timestamp order that describe when a function is entered or exited.

Each log is a string with this format:

“{function_id}:{”start” | “end”}:{timestamp}”.

For example, * “0:start:3” means the function with id 0 started at the beginning of timestamp 3. * “1:end:2” means the function with id 1 ended at the end of timestamp 2.

A function’s exclusive time is the number of units of time spent in this function. Note that this does not include any recursive calls to child functions.

The CPU is single threaded which means that only one function is being executed at a given time unit.

Return the exclusive time of each function, sorted by their function id.

Example 1:

Input: n = 2, logs = [“0:start:0”, “1:start:2”, “1:end:5”, “0:end:6”]

Output: [3, 4]

Explanation:

  • Function 0 starts at time 0, then it executes 2 units of time and reaches the end of time 1.

  • Now function 0 calls function 1, function 1 starts at time 2, executes 4 units of time and end at time 5.

  • Function 0 is running again at time 6, and also end at the time 6, thus executes 1 unit of time.

  • So function 0 totally execute 2 + 1 = 3 units of time, and function 1 totally execute 4 units of time.

Notes:

  • Input logs will be sorted by timestamp, NOT log id.

  • Your output should be sorted by function id, which means the 0th element of your output corresponds to the exclusive time of function 0.

  • Two functions won’t start or end at the same time.

  • Functions could be called recursively, and will always end.

  • 1 <= n <= 100

1. Using Stack [Time Limit Exceeded]

2 Better Approach

Algorithm

In the last approach, for every function on the top of the stackstack, we incremented the current time and the exclusive time of this same function till the current time became equal to the start/end time of the next function.

Instead of doing this incrementing step by step, we can directly use the difference between the next function’s start/stop time and the current function’s start/stop time. The rest of the process remains the same as in the last approach.

The following animation illustrates the process.

See: https://leetcode.com/problems/exclusive-time-of-functions/solution/

[5]:

class Solution2(object):
    """
    Time: O(N). We iterate over the entire logslogs array just once.
          Here, nn refers to the number of elements in the logslogs list.
    Space: The stackstack can grow upto a depth of atmost n/2.
          Here, nn refers to the number of elements in the given logslogs list.
    """
    def exclusiveTime(self, n, logs):
        """
        :type n: int
        :type logs: List[str]
        :rtype: List[int]
        """
        result = [0] * n
        stk, prev = [], 0

        for log in logs:
            tokens = log.split(":")
            if tokens[1] == "start":
                if stk:
                    result[stk[-1]] += int(tokens[2]) - prev
                stk.append(int(tokens[0]))
                prev = int(tokens[2])
            else:
                result[stk.pop()] += int(tokens[2]) - prev + 1
                prev = int(tokens[2]) + 1
        return result

[6]:

s = Solution2()
n = 2
logs = ["0:start:0", "1:start:2", "1:end:5", "0:end:6"]
assert s.exclusiveTime(n, logs) == [3, 4]